package me.huangxiang.data_structure_and_algorithm.sort;

/**
 * QuickSort(A, l, r)
 * if l < r
 *      s <-- Partition(A, l, r)
 *      QuickSort(A, l, s - 1)
 *      QuickSort(A, s + 1, r)
 */


public class QuickSort {

    public static void quickSortV1(int[] A, int l, int r){
        if (l < r){ // 确定递归退出条件
            int q = partition(A, l, r);
            quickSortV1(A, l, q - 1);
            quickSortV1(A, q + 1, r);
        }
    }


    public static int partition(int[] A, int l, int r){
        // 挖坑 + 分治
        int i = l;
        int j = r;
        int x = A[l]; // 先挖一个坑

        while (i < j){
            // 从后往前找到第一个小于x的值
            while (i < j && A[j] >= x){

                j--;
            }
            // 用找到的数去填之前挖的坑，找到的位置留下用一个坑。
            if (i < j){
                A[i] = A[j];
                i++;
            }

            // 从前往后找一个数去填坑
            while (i < j && A[i] < x){
                i++;
            }
            if (i < j){
                A[j] = A[i];
                j--;
            }
        }
        // 这个时候退出必然是i == j
        // 两头相会找到放主元素的位置，返回主元素位置
        A[i] = x;
        return i;
    }

    public static void exchange(int[] A, int s, int d){
        int tmp = A[s];
        A[s] = A[d];
        A[d] = tmp;
    }
}
